#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <vector>
#include <queue>
#include <cassert>
using namespace std;

struct ListNode
{
	int val;
	ListNode* next;
	ListNode(int v):val(v),next(NULL){}
	/*bool operator<=(const ListNode* node)
	{
		return val>=node->val;
	}*/
};

struct ListNodePtrComp
{
	bool operator()(const ListNode* a, const ListNode* b)
	{
		assert(a&&b);
		return (a->val) >= (b->val);
	}
};

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) 
	{
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		if(lists.empty())
			return NULL;
        
		priority_queue<ListNode*,vector<ListNode*>,ListNodePtrComp> curNodes;

		for(size_t i=0;i<lists.size();i++)
		{
			if(lists[i])
				curNodes.push(lists[i]);
		}
		
		ListNode head(0);
		ListNode* cur = &head;

		while(!curNodes.empty())
		{
			cur->next = curNodes.top();
			curNodes.pop();
			cur = cur->next;
			if(cur->next)
				curNodes.push(cur->next);
		}

		return head.next;
    }
};
#endif
